// Package medium
// url:https://leetcode.cn/problems/insert-delete-getrandom-o1/description/
package medium

import "math/rand"

type RandomizedSet380 struct {
	nums    []int
	indices map[int]int
}

func Constructor() RandomizedSet380 {
	r := new(RandomizedSet380)
	r.nums = make([]int, 0)
	r.indices = make(map[int]int)
	return *r
}

func (s *RandomizedSet380) Insert(val int) bool {

	if _, ok := s.indices[val]; ok {
		return false
	}

	s.indices[val] = len(s.nums)
	s.nums = append(s.nums, val)

	return true
}

func (s *RandomizedSet380) Remove(val int) bool {

	index, ok := s.indices[val]
	if !ok {
		return false
	}

	last := len(s.nums) - 1
	lastVal := s.nums[last]

	s.nums[index] = lastVal
	s.indices[lastVal] = index

	s.nums = s.nums[:last]
	delete(s.indices, val)

	return true
}

func (s *RandomizedSet380) GetRandom() int {
	return s.nums[rand.Intn(len(s.indices))]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
